马尔可夫链

Markov chain MC
具有无记忆性的离散参数随机过程

过去所有的信息都已经被保存到了现在的状态，基于现在就可以预测未来。

The future is independent of the past， given the present.
未来独立于过去，只基于当下。

一、马尔可夫性

Markov Property

马尔可夫性：马尔可夫链为状态空间中经过从一个状态到另一个状态的转换的随机过程，该过程要求具备“无记忆性 ”，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

\begin{array}{r} P {X_{t + 1} = j ∣ X_{0} = i_{0}, \dots, X_{t - 1} = i_{t - 1}, X_{t} = i} = P {X_{t + 1} = j ∣ X_{t} = i} \end{array}

二、转移概率

1. 一步转移概率

此条件概率称为马尔可夫链在时刻 $t$ 处于状态 $i$ 条件下，在时刻 $t + 1$ 转移到状态 $j$ 的转移概率：

\begin{array}{r} p_{i j} = P {X_{t + 1} = j ∣ X_{t} = i} \end{array}

通常将一步转移概率排成无穷维度的矩阵，作为时齐马尔可夫链的状态转移矩阵：（当状态空间为有限集时， $P$ 就为有限矩阵，阶数等于状态空间的状态数）

\begin{array}{r} P = (\begin{array}{c} p_{00} & p_{01} & \dots & p_{0 j} & \dots \\ p_{10} & p_{11} & \dots & p_{1 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 0} & p_{i 1} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array}) \end{array}

马尔可夫链在时刻 $t$ 从任何一个状态 $i$ 出发，到另一个时刻 $t + 1$ 必然转移到某状态 $j$ 中（必然事件），对于任意状态 $i, j, p_{i j} \geq 0$ , 有：

\begin{array}{r} \sum_{j = 0}^{+ \infty} p_{i j} = 1 \end{array}

这意味着状态转移矩阵的每一行的元素之和都为 1

2. 多步转移概率

$n$ 步转移概率定义为：马尔可夫链 $X_{t}$ 在时刻 $t$ 处于状态 $i$ 的条件下，经过 $n$ 步转移到达状态 $j$ 的转移概率。如果 $X_{t}$ 为时齐的，则可以简单记为 $p_{i j} (n)$

\begin{array}{r} p_{i j} (t, t + n) = p_{i j} (n) = P {X_{t + n} = j ∣ X_{t} = i} \end{array}

Champman-Kolmogorov Equation C-K 方程：

\begin{array}{r} p_{i j} (n + m) = \sum_{k = 0}^{\infty} p_{i k} (n) p_{k j} (m) \end{array}

写为矩阵的形式，进一步由递推关系知：时齐马尔可夫链的 $n$ 步转移概率是一步转移概率矩阵的 $n$ 次方：（矩阵的幂可以利用矩阵对角化方便地计算）

\begin{array}{r} P (n + m) = P (n) P (m) \Rightarrow P (n) = P P (n - 1) = P^{n} \end{array}

对马尔可夫链 $X_{t}$ ，定义 $p_{j} (0)$ 为初始一维分布， $p_{j} (n)$ 为任一时刻 $n$ 的一维分布：

p_{j} (0) = P {X_{0} = j} p_{j} (n) = P {X_{n} = j}, j \in I

时齐马尔可夫链在任一时刻 $n$ 的一维分布由它的初始分布和 $n$ 步状态转移概率矩阵确定：

\begin{aligned} P {X_{n} = j} = \sum_{i = 0}^{\infty} P {X_{n} = j ∣ X_{0} = i} P {X_{0} = i} \\ \Rightarrow p_{j} (n) = \sum_{i = 0}^{\infty} p_{i} (0) p_{i j} (n) \Rightarrow p (n) = p (0) P (n) \end{aligned}

\begin{array}{r} p (n) = {(\begin{array}{c} p_{0} (n) \\ p_{1} (n) \\ ⋮ \\ p_{j} (n) \\ ⋮ \end{array})}^{T} = {(\begin{array}{c} p_{0} (0) \\ p_{1} (0)) \\ ⋮ \\ p_{j} (0) \\ ⋮ \end{array})}^{T} {(\begin{array}{c} p_{00} & p_{01} & \dots & p_{0 j} & \dots \\ p_{10} & p_{11} & \dots & p_{1 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 0} & p_{i 1} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array})}^{n} \end{array}

三、遍历性

主要研究当步数趋于无穷时的转移概率

遍历性：对于固定的状态 $j$ ，不管链在某一时刻从什么状态出发，通过长时间转移，到达状态 $j$ 的概率都接近 $π_{j}$

如果对于所有 $i, j \in I$ ，转移概率 $p_{i j}$ 存在极限，则称该马尔科夫链具有遍历性，进一步得到马尔可夫链的极限分布 $π$ ：

π_{j} = lim_{n \to \infty} p_{i j} (n) \Rightarrow π = (\begin{matrix} π_{0} & π_{1} & \dots & π_{j} & \dots \end{matrix}) \sum_{j}^{} π_{j} = 1

\begin{array}{r} π = π P π_{j} = \sum_{i = 0}^{N} π_{i} p_{i j} \sum_{j = 0}^{N} π_{j} = 1 \end{array}

基本应用

用于动力系统、化学反应、排队论、市场行为和信息检索的数学建模
马尔可夫链可被应用于蒙特卡洛方法中，形成马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）

此外作为结构最简单的马尔可夫模型（Markov model）
一些机器学习算法，以马尔可夫链为理论基础，例如
隐马尔可夫模型（Hidden Markov Model, HMM）
马尔可夫随机场（Markov Random Field, MRF）
马尔可夫决策过程（Markov decision process, MDP）